package com.example.Arithmetic.Lettcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 日期：2023/12/28
 * 时间：20:17
 * 描述：数组元素之间的最大差值，要求线性时间O(log n),桶排序实现
 * 先排序，然后遍历后一个减去前一个
 */
public class E01Lettcode164_1 {
    public int maximumGap(int[] nums) {
        if (nums.length<2){
            return 0;
        }
//        寻找最大值
        int max = 0;
        for (int i : nums) {
            max = Math.max(max, i);
        }
//        初始化桶
        ArrayList[] arrayList = new ArrayList[10];
        for (int i = 0; i < 10; i++) {
            arrayList[i] = new ArrayList();
        }
//        从各位开始拆，依次拆分每一位
        int c = 1;
        while (c <= max) {
            for (int i : nums) {
                arrayList[i / c % 10].add(i);
            }
            int k = 0;
            for (ArrayList<Integer> list : arrayList) {
                for (int i : list) {
                    nums[k++] = i;
                }
                System.out.println(Arrays.toString(nums));
//                必须清理
                list.clear();
            }
            c = c * 10;
        }
        System.out.println(Arrays.toString(nums));
//        寻找最大差值
        max = 0;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i] - nums[i - 1]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{100,3,2,1};
        E01Lettcode164_1 e01Lettcode164 = new E01Lettcode164_1();
        int i = e01Lettcode164.maximumGap(arr1);
        System.out.println(i);
    }
}

